// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
	"sync"
)

// BinarySearchTree 表示支持插入键值对的二叉搜索树。
type BinarySearchTree struct {
	rootNode *TreeNode
	lock     sync.RWMutex
}

// TreeNode 表示二叉搜索树中的一个节点，有一个键值对，以及左右子节点
type TreeNode struct {
	key       int
	value     int
	leftNode  *TreeNode
	rightNode *TreeNode
}

// InsertElement 将一个新的键值对插入到二叉搜索树中
func (tree *BinarySearchTree) InsertElement(key int, value int) {
	tree.lock.Lock()
	defer tree.lock.Unlock()

	var newNode = &TreeNode{key: key, value: value}
	if tree.rootNode == nil {
		tree.rootNode = newNode
	} else {
		InsertNode(tree.rootNode, newNode)
	}
}

// InsertNode 将一个新节点作为指定父节点的子节点插入到二叉搜索树中
func InsertNode(parentNode *TreeNode, newNode *TreeNode) {

	if newNode.key < parentNode.key {
		if parentNode.leftNode == nil {
			parentNode.leftNode = newNode
		} else {
			InsertNode(parentNode.leftNode, newNode)
		}
	}

	if newNode.key > parentNode.key {
		if parentNode.rightNode == nil {
			parentNode.rightNode = newNode
		} else {
			InsertNode(parentNode.rightNode, newNode)
		}
	}
}

// 中序遍历
func (tree *BinarySearchTree) InOrderTraverseTree() {
	tree.lock.RLock()
	defer tree.lock.RUnlock()
	inOrderTraverseTree(tree.rootNode)
}

// 中序遍历函数
func inOrderTraverseTree(treeNode *TreeNode) {
	if treeNode != nil {
		inOrderTraverseTree(treeNode.leftNode)
		inOrderTraverseTree(treeNode.rightNode)
		fmt.Println(treeNode.value)
	}
}

// 先序遍历
func (tree *BinarySearchTree) PreOrderTraverseTree() {
	tree.lock.RLock()
	defer tree.lock.RUnlock()
	preOrderTraverseTree(tree.rootNode)
}

// 先序遍历函数
func preOrderTraverseTree(treeNode *TreeNode) {
	if treeNode != nil {
		preOrderTraverseTree(treeNode.leftNode)
		preOrderTraverseTree(treeNode.rightNode)
		fmt.Println(treeNode.value)
	}
}

// 后序遍历
func (tree *BinarySearchTree) PostOrderTraverseTree() {
	tree.lock.Lock()
	defer tree.lock.Unlock()
	postOrderTraverseTree(tree.rootNode)
}

// 后序遍历函数
func postOrderTraverseTree(treeNode *TreeNode) {
	if treeNode != nil {
		postOrderTraverseTree(treeNode.leftNode)
		postOrderTraverseTree(treeNode.rightNode)
		fmt.Println(treeNode.value)
	}
}

// 获取最小节点
func (tree *BinarySearchTree) MinNode() *TreeNode {
	tree.lock.RLock()
	defer tree.lock.RUnlock()
	return minNode(tree.rootNode)
}

func minNode(treeNode *TreeNode) *TreeNode {
	if treeNode.leftNode != nil {
		return minNode(treeNode.leftNode)
	} else {
		return treeNode
	}
}

// 获取最大节点
func (tree *BinarySearchTree) MaxNode() *TreeNode {
	tree.lock.RLock()
	defer tree.lock.RUnlock()
	return maxNode(tree.rootNode)
}

func maxNode(treeNode *TreeNode) *TreeNode {
	if treeNode.rightNode != nil {
		return maxNode(treeNode.rightNode)
	} else {
		return treeNode
	}
}

// 搜索节点方法
func (tree *BinarySearchTree) SearchNode(key int) bool {
	tree.lock.RLock()
	defer tree.lock.RUnlock()
	return searchNode(tree.rootNode, key)
}

// 搜索节点函数
func searchNode(treeNode *TreeNode, key int) bool {
	if treeNode == nil {
		return false
	}
	if treeNode.key == key {
		return true
	}
	if key < treeNode.key {
		return searchNode(treeNode.leftNode, key)
	}
	if key > treeNode.key {
		return searchNode(treeNode.rightNode, key)
	}
	return true
}

// 删除节点方法
func (tree *BinarySearchTree) RemoveNode(key int) {
	tree.lock.Lock()
	defer tree.lock.Unlock()
	removeNode(tree.rootNode, key)
}

// 删除节点函数
func removeNode(treeNode *TreeNode, key int) *TreeNode {
	if treeNode == nil {
		return nil
	}
	if key < treeNode.key {
		treeNode.leftNode = removeNode(treeNode.leftNode, key)
		return treeNode
	}
	if key > treeNode.key {
		treeNode.rightNode = removeNode(treeNode.rightNode, key)
		return treeNode
	}

	if treeNode.leftNode == nil && treeNode.rightNode == nil {
		treeNode = nil
		return nil
	}
	if treeNode.leftNode == nil {
		treeNode = treeNode.rightNode
		return treeNode
	}
	if treeNode.rightNode == nil {
		treeNode = treeNode.leftNode
		return treeNode
	}
	var leftmostrightNode *TreeNode
	leftmostrightNode = treeNode.rightNode
	for {

		if leftmostrightNode != nil && leftmostrightNode.leftNode != nil {
			leftmostrightNode = leftmostrightNode.leftNode
		} else {
			break
		}
	}
	treeNode.key, treeNode.value = leftmostrightNode.key, leftmostrightNode.value
	treeNode.rightNode = removeNode(treeNode.rightNode, treeNode.key)
	return treeNode
}

func main() {
	root := &TreeNode{0, 9, nil, nil}
	node1 := &TreeNode{1, 8, nil, nil}
	node2 := &TreeNode{2, 12, nil, nil}
	node3 := &TreeNode{3, 11, nil, nil}
	node4 := &TreeNode{4, 13, nil, nil}
	node6 := &TreeNode{5, 14, nil, nil}
	root.leftNode = node1
	root.rightNode = node2
	node2.leftNode = node3
	node2.rightNode = node4
	node3.rightNode = node6
	var lock sync.RWMutex
	bst := BinarySearchTree{root, lock}
	bst.PreOrderTraverseTree()
	res := bst.MaxNode()
	fmt.Println(res)
}

//$ go run binarySearchTree.go
//8
//14
//11
//13
//12
//9
//&{4 13 <nil> <nil>}
